#include <dbg.h>

#include <cassert>

using namespace std;

class Solution {
public:
    string findLongestWord(string s, vector<string>& dictionary) {
        int sSize = s.size();

        string res;
        for (string dic : dictionary) {
            int indexS = 0;  // 双指针
            int indexDic = 0;
            while (indexS < sSize && indexDic < dic.size()) {
                if (s[indexS] == dic[indexDic]) {  // 字符匹配, 双指针同时后移
                    ++indexDic;
                }
                ++indexS;  // 字符不匹配, s 指针后移
            }
            if (indexDic == dic.size()) {  // 匹配成功，更新结果
                if (dic.size() > res.size() /* 最长单词 */ ||
                    (dic.size() == res.size() && dic < res) /* 字母序最小 */) {
                    res = dic;
                }
            }
        }
        return res;
    }
};

#ifdef sort
class Solution {
public:
    string findLongestWord(string s, vector<string>& dictionary) {
        sort(dictionary.begin(),
             dictionary.end(),
             [](const string& a, const string& b) {
                 return a.size() > b.size() /* 最长单词 */ ||
                        (a.size() == b.size() && a < b) /* 字母序最小 */;
             });
        int sSize = s.size();
        for (string dic : dictionary) {
            int indexS = 0;  // 双指针
            int indexDic = 0;
            while (indexS < sSize && indexDic < dic.size()) {
                if (s[indexS] == dic[indexDic]) {  // 字符匹配, 双指针同时后移
                    ++indexDic;
                }
                ++indexS;  // 字符不匹配, s 指针后移
            }
            if (indexDic == dic.size()) {  // 匹配成功，更新结果
                return dic;
            }
        }
        return "";
    }
};
#endif

int main() {
    Solution s;

    string s1 = "abpcplea";
    string s2 = "abpcplea";

    vector<string> dictionary1 = {"ale", "apple", "monkey", "plea"};
    vector<string> dictionary2 = {"a", "b", "c"};

    assert(s.findLongestWord(s1, dictionary1) == "apple");
    assert(s.findLongestWord(s2, dictionary2) == "a");

    return 0;
}